package cn.zhaoyuening.algorithms.sort;

/**
 * Created by Zhao on 2017/3/25.
 * 归并排序
 */
public class MergeSort<T> implements Sort<T>{
    private Comparable<T>[] tmpArr;


    @Override
    public Comparable<T>[] sort(Comparable<T>[] comparables) {
        tmpArr = new Comparable[comparables.length];
        if (comparables.length <= 1) {
            return comparables;
        }
        int mid = comparables.length/2;
        sort(comparables, 0, mid, comparables.length - 1);
        return null;
    }

    private Comparable<T>[] sort(Comparable<T>[] comparables, int si, int mid, int ei) {
        if (ei<=si)
            return comparables;
        int mid1 = (si+mid)/2;
        int mid2 = (ei+mid+1)/2;
        sort(comparables, si, mid1, mid);
        sort(comparables, mid + 1, mid2, ei);
        merge(comparables, si, mid, ei);
        return comparables;
    }

    private Comparable<T>[] merge(Comparable<T>[] comparables, int si, int mid, int ei){
        int i=si,j=mid+1,x=si;
        for(;i<=mid&&j<=ei;x++){
            if (comparables[i].compareTo((T) comparables[j])<0){
                tmpArr[x]=comparables[i];
                i++;
            }else{
                tmpArr[x] = comparables[j];
                j++;
            }
        }
        if (i>mid){
            for (;j<=ei;x++,j++){
                tmpArr[x] = comparables[j];
            }
        }else{
            for (;i<=mid;x++,i++){
                tmpArr[x] = comparables[i];
            }
        }

        for(i=si;i<=ei;i++) {
            comparables[i] = tmpArr[i];
        }

        return comparables;
    }


}
